import java.util.List;

public class Leetcode {
}

//递归方式解决

//leetcode:面试题 08.06 汉诺塔问题
class Solution1 {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        dfs(A,B,C,A.size());
    }

    public void dfs(List<Integer> A, List<Integer> B, List<Integer> C,int n){
        if(n == 1){
            C.add(A.remove(A.size()-1));
            return;
        }
        dfs(A,C,B,n-1);
        C.add(A.remove(A.size()- 1));
        dfs(B,A,C,n-1);
    }
}

//leetcode:21:合并两个有序链表
class Solution2 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;

        if(list1.val < list2.val){
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }else{
            list2.next = mergeTwoLists(list2.next,list1);
            return list2;
        }
    }
}

//leetcode:206:反转链表
class Solution3 {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }

        ListNode newhead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newhead;
    }
}

//leetcode:24:两两交换链表中的结点
class Solution4 {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }

        ListNode tmp = swapPairs(head.next.next);
        ListNode cur = head.next;
        cur.next = head;
        head.next = tmp;
        return cur;
    }
}

//leetcode:50:Pow(x,n);
class Solution {
    public double myPow(double x, int n) {
        return n < 0 ? 1.0 /pow(x,-n) : pow(x,n);
    }
    public double pow(double x,int n){
        if(n == 0) return 1.0;
        double tmp = pow(x,n/2);
        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
    }
}